/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/gas-station
   @Language: C++
   @Datetime: 17-04-04 17:20
   */

class Solution {
public:
	/**
	 * @param gas: a vector of integers
	 * @param cost: a vector of integers
	 * @return: an integer 
	 * Tip: There is only one answer !!
	 * Assume id=i is answer, if start from i-1 can reach to i,
	 *      the i-1 is also answer. return any answer is correct.
	 */
	int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
		// write your code here
		int sum=0, id=0, total=0;
		for(int i=0; i<gas.size(); ++i){
			sum += gas[i]-cost[i];
			total += gas[i]-cost[i];
			if (sum>=0) continue;
			sum=0;
			id=i+1;
		}
		return total>-1? id : -1;
	}
};
